\begin{frame}
\frametitle{Sudoku deterministic process}

Let $T = (\Sigma,\Gamma,\Theta,\pi)$ be a domino tiling system. For picture
$p\in\Sigma$ is $s_p$ a local picture of the same size in which we initialize
every position $(i, j)$ by the set $s_p(i, j) := \pi^{-1}(p(i, j))\in 2^\Gamma$ of
possible pre image symbols. 

\setlength{\tabcolsep}{3pt} 
\begin{define}[Sudoku-deterministic process\cite{borchert2006deterministically}]
For $s,s'\in(2^\Gamma)^{**}$ (of the same size) we allow a step $\hat{s}
\underset{sd(T)}{\Rightarrow} \hat{s}'$ if following conditions holds for all
positions $(i, j)$ of s':
\begin{align*}
s'(i,j) = &\{x\in s(i,j)\mid\exists\gamma_1, \gamma_2, \gamma_3, \gamma_4\in
\Gamma\cup\{\#\}\text{ such that }\\
&\gamma_1\in\hat{s}(i + 1, j), \gamma_2\in\hat{s}(i - 1, j),
\gamma_3\in\hat{s}(i, j + 1), \gamma_4\in\hat{s}(i, j - 1)\\
&\text{ and }
\begin{tabular}{|c|c|} 
\hline
 x & $\gamma_1$ \\
\hline 
\end{tabular}, 
\begin{tabular}{|c|c|} 
\hline 
$\gamma_2$ & x \\
\hline 
\end{tabular}, 
\begin{tabular}{|c|} 
\hline 
x \\ 
\hline 
$\gamma_3$ \\
\hline 
\end{tabular}, 
\begin{tabular}{|c|} 
\hline 
$\gamma_4$ \\ 
\hline 
x \\
\hline 
\end{tabular}
\in\Theta\}.
\end{align*}
\end{define}
\setlength{\tabcolsep}{6pt} 
\end{frame}

\begin{frame}
\frametitle{Deterministic process}
\begin{define}[deterministic process\cite{borchert2006deterministically}]
For $s,s'\in(2^\Gamma)^{**}$ (of the same size) we allow a step $\hat{s}
\underset{d(T)}{\Rightarrow} \hat{s}'$ if $\hat{s}
\underset{sd(T)}{\Rightarrow} \hat{s}''$ and for all positions
$(i, j)$ of $s'$ we define $s'(i, j) := s''(i, j)$ if $\mid s''(i, j)\mid = 1$
or $\hat{s}'(i, j) = \hat{s}(i, j)$
\end{define}


A Sudoku-deterministically recognizable picture language
$\mathcal{L}_{sd}(T)$ over a domino tiling system $T = (\Sigma, \Gamma,
\Theta, \pi)$ is $\mathcal{L}_{sd}(T) := \{p\in\Sigma^{**}\mid\exists
p'\in\mathcal{L}(T)$ s.t.
$\hat{s}_p\overset{*}{\underset{sd(T)}{\Rightarrow}} \{\hat{p}'\}\}$. The
language $\mathcal{L}_{d}(T)$ is defined the same way using
$\overset{*}{\underset{d(T)}{\Rightarrow}}$ instead of
$\overset{*}{\underset{sd(T)}{\Rightarrow}}$.
\end{frame}

\begin{frame}
\frametitle{Language hierarchy}
The family of all Sudoku-deterministically recognizable picture languages is
denoted by SDREC. Every language in SDREC (and therefore DREC) is computable
PTIME.

\begin{thm}[\cite{borchert2006deterministically}]
4AFA $\subseteq$ SDREC, \\
DREC $\subseteq$ SDREC, \\
DREC $\subseteq$ REC, \\
DREC $\subseteq$ co-REC.
\end{thm}
\end{frame}